package leetcode.editor.cn;
//n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。 
//
// 给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。 
//
// 
//
// 
// 
// 示例 1： 
// 
// 
//输入：n = 4
//输出：2
//解释：如上图所示，4 皇后问题存在两个不同的解法。
// 
// 
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 9 
// 
//
// Related Topics 回溯 👍 427 👎 0


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution116 {

    int res = 0;

    public int totalNQueens(int n) {
        List<String> board = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                sb.append('.');
            }
            board.add(sb.toString());
        }
        backtrack(board, 0);
        return res;

    }

    private void backtrack(List<String> board, int i) {
        if (board.size() == i) {
            res++;
            return;
        }

        for (int j = 0; j < board.size(); j++) {
            if (!isValid(board, i, j)) {
                continue;
            }
            // 做选择
            StringBuilder sb = new StringBuilder(board.get(i));
            sb.setCharAt(j, 'Q');
            board.set(i, sb.toString());

            backtrack(board, i + 1);
            sb.setCharAt(j, '.');
            board.set(i, sb.toString());


        }
    }

    private boolean isValid(List<String> board, int row, int col) {
        StringBuilder sb = new StringBuilder(board.get(row));

        for (int k = 0; k < board.size(); k++) {
            if (board.get(k).charAt(col) == 'Q') {
                return false;
            }
        }

        /* 检查右上方是否有皇后互相冲突 */
        for (int i = row - 1, j = col + 1;
             i >= 0 && j < board.size(); i--, j++) {
            if (board.get(i).charAt(j) == 'Q') {
                return false;
            }
        }

        /* 检查左上方是否有皇后互相冲突 */
        for (int i = row - 1, j = col - 1;
             i >= 0 && j >= 0; i--, j--) {
            if (board.get(i).charAt(j) == 'Q') {
                return false;
            }
        }

        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
